home *** CD-ROM | disk | FTP | other *** search
/ Windows Expert / Windows Expert.iso / windownt / tusrc.zip / LIB / MEMCMP.C < prev    next >
C/C++ Source or Header  |  1993-09-18  |  8KB  |  325 lines
  1. /* Copyright (C) 1991, 1993 Free Software Foundation, Inc.
  2.    Contributed by Torbjorn Granlund (tege@sics.se).
  3.  
  4. The GNU C Library is free software; you can redistribute it and/or
  5. modify it under the terms of the GNU Library General Public License as
  6. published by the Free Software Foundation; either version 2 of the
  7. License, or (at your option) any later version.
  8.  
  9. The GNU C Library is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12. Library General Public License for more details.
  13.  
  14. You should have received a copy of the GNU Library General Public
  15. License along with the GNU C Library; see the file COPYING.LIB.  If
  16. not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  17. Cambridge, MA 02139, USA.  */
  18.  
  19. #ifdef HAVE_CONFIG_H
  20. #include "config.h"
  21. #endif
  22.  
  23. #if defined (HAVE_STRING_H) || defined (_LIBC)
  24. #include <string.h>
  25. #endif
  26.  
  27. #ifdef _LIBC
  28.  
  29. #include <memcopy.h>
  30.  
  31. #else    /* Not in the GNU C library.  */
  32.  
  33. #include <sys/types.h>
  34.  
  35. /* Type to use for aligned memory operations.
  36.    This should normally be the biggest type supported by a single load
  37.    and store.  */
  38. #define    op_t    unsigned long int
  39. #define OPSIZ    (sizeof(op_t))
  40.  
  41. /* Threshold value for when to enter the unrolled loops.  */
  42. #define    OP_T_THRES    16
  43.  
  44. /* Type to use for unaligned operations.  */
  45. typedef unsigned char byte;
  46.  
  47. #ifdef WORDS_BIGENDIAN
  48. #define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
  49. #else
  50. #define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
  51. #endif
  52.  
  53. #endif    /* In the GNU C library.  */
  54.  
  55.  
  56. /* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */
  57.  
  58. /* The strategy of this memcmp is:
  59.  
  60.    1. Compare bytes until one of the block pointers is aligned.
  61.  
  62.    2. Compare using memcmp_common_alignment or
  63.       memcmp_not_common_alignment, regarding the alignment of the other
  64.       block after the initial byte operations.  The maximum number of
  65.       full words (of type op_t) are compared in this way.
  66.  
  67.    3. Compare the few remaining bytes.  */
  68.  
  69. /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
  70.    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
  71.    memory operations on `op_t's.  */
  72. #ifdef    __GNUC__
  73. __inline
  74. #endif
  75. static int
  76. memcmp_common_alignment (srcp1, srcp2, len)
  77.      long int srcp1;
  78.      long int srcp2;
  79.      size_t len;
  80. {
  81.   op_t a0, a1;
  82.   op_t b0, b1;
  83.   op_t res;
  84.  
  85.   switch (len % 4)
  86.     {
  87.     case 2:
  88.       a0 = ((op_t *) srcp1)[0];
  89.       b0 = ((op_t *) srcp2)[0];
  90.       srcp1 -= 2 * OPSIZ;
  91.       srcp2 -= 2 * OPSIZ;
  92.       len += 2;
  93.       goto do1;
  94.     case 3:
  95.       a1 = ((op_t *) srcp1)[0];
  96.       b1 = ((op_t *) srcp2)[0];
  97.       srcp1 -= OPSIZ;
  98.       srcp2 -= OPSIZ;
  99.       len += 1;
  100.       goto do2;
  101.     case 0:
  102.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  103.     return 0;
  104.       a0 = ((op_t *) srcp1)[0];
  105.       b0 = ((op_t *) srcp2)[0];
  106.       goto do3;
  107.     case 1:
  108.       a1 = ((op_t *) srcp1)[0];
  109.       b1 = ((op_t *) srcp2)[0];
  110.       srcp1 += OPSIZ;
  111.       srcp2 += OPSIZ;
  112.       len -= 1;
  113.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  114.     goto do0;
  115.       /* Fall through.  */
  116.     }
  117.  
  118.   do
  119.     {
  120.       a0 = ((op_t *) srcp1)[0];
  121.       b0 = ((op_t *) srcp2)[0];
  122.       res = a1 - b1;
  123.       if (res != 0)
  124.     return res;
  125.     do3:
  126.       a1 = ((op_t *) srcp1)[1];
  127.       b1 = ((op_t *) srcp2)[1];
  128.       res = a0 - b0;
  129.       if (res != 0)
  130.     return res;
  131.     do2:
  132.       a0 = ((op_t *) srcp1)[2];
  133.       b0 = ((op_t *) srcp2)[2];
  134.       res = a1 - b1;
  135.       if (res != 0)
  136.     return res;
  137.     do1:
  138.       a1 = ((op_t *) srcp1)[3];
  139.       b1 = ((op_t *) srcp2)[3];
  140.       res = a0 - b0;
  141.       if (res != 0)
  142.     return res;
  143.  
  144.       srcp1 += 4 * OPSIZ;
  145.       srcp2 += 4 * OPSIZ;
  146.       len -= 4;
  147.     }
  148.   while (len != 0);
  149.  
  150.   /* This is the right position for do0.  Please don't move
  151.      it into the loop.  */
  152.  do0:
  153.   return a1 - b1;
  154. }
  155.  
  156.  
  157. /* SRCP2 should be aligned for memory operations on `op_t',
  158.    but SRCP1 *should be unaligned*.  */
  159.  
  160. #ifdef    __GNUC__
  161. __inline
  162. #endif
  163. static int
  164. memcmp_not_common_alignment (srcp1, srcp2, len)
  165.      long int srcp1;
  166.      long int srcp2;
  167.      size_t len;
  168. {
  169.   op_t a0, a1, a2, a3;
  170.   op_t b0, b1, b2, b3;
  171.   op_t res;
  172.   op_t x;
  173.   int shl, shr;
  174.  
  175.   /* Calculate how to shift a word read at the memory operation
  176.      aligned srcp1 to make it aligned for comparison.  */
  177.  
  178.   shl = 8 * (srcp1 % OPSIZ);
  179.   shr = 8 * OPSIZ - shl;
  180.  
  181.   /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
  182.      it points in the middle of.  */
  183.   srcp1 &= -OPSIZ;
  184.  
  185.   switch (len % 4)
  186.     {
  187.     case 2:
  188.       a1 = ((op_t *) srcp1)[0];
  189.       a2 = ((op_t *) srcp1)[1];
  190.       b2 = ((op_t *) srcp2)[0];
  191.       srcp1 -= 1 * OPSIZ;
  192.       srcp2 -= 2 * OPSIZ;
  193.       len += 2;
  194.       goto do1;
  195.     case 3:
  196.       a0 = ((op_t *) srcp1)[0];
  197.       a1 = ((op_t *) srcp1)[1];
  198.       b1 = ((op_t *) srcp2)[0];
  199.       srcp2 -= 1 * OPSIZ;
  200.       len += 1;
  201.       goto do2;
  202.     case 0:
  203.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  204.     return 0;
  205.       a3 = ((op_t *) srcp1)[0];
  206.       a0 = ((op_t *) srcp1)[1];
  207.       b0 = ((op_t *) srcp2)[0];
  208.       srcp1 += 1 * OPSIZ;
  209.       goto do3;
  210.     case 1:
  211.       a2 = ((op_t *) srcp1)[0];
  212.       a3 = ((op_t *) srcp1)[1];
  213.       b3 = ((op_t *) srcp2)[0];
  214.       srcp1 += 2 * OPSIZ;
  215.       srcp2 += 1 * OPSIZ;
  216.       len -= 1;
  217.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  218.     goto do0;
  219.       /* Fall through.  */
  220.     }
  221.  
  222.   do
  223.     {
  224.       a0 = ((op_t *) srcp1)[0];
  225.       b0 = ((op_t *) srcp2)[0];
  226.       x = MERGE(a2, shl, a3, shr);
  227.       res = x - b3;
  228.       if (res != 0)
  229.     return res;
  230.     do3:
  231.       a1 = ((op_t *) srcp1)[1];
  232.       b1 = ((op_t *) srcp2)[1];
  233.       x = MERGE(a3, shl, a0, shr);
  234.       res = x - b0;
  235.       if (res != 0)
  236.     return res;
  237.     do2:
  238.       a2 = ((op_t *) srcp1)[2];
  239.       b2 = ((op_t *) srcp2)[2];
  240.       x = MERGE(a0, shl, a1, shr);
  241.       res = x - b1;
  242.       if (res != 0)
  243.     return res;
  244.     do1:
  245.       a3 = ((op_t *) srcp1)[3];
  246.       b3 = ((op_t *) srcp2)[3];
  247.       x = MERGE(a1, shl, a2, shr);
  248.       res = x - b2;
  249.       if (res != 0)
  250.     return res;
  251.  
  252.       srcp1 += 4 * OPSIZ;
  253.       srcp2 += 4 * OPSIZ;
  254.       len -= 4;
  255.     }
  256.   while (len != 0);
  257.  
  258.   /* This is the right position for do0.  Please don't move
  259.      it into the loop.  */
  260.  do0:
  261.   x = MERGE(a2, shl, a3, shr);
  262.   return x - b3;
  263. }
  264.  
  265. int
  266. memcmp (s1, s2, len)
  267.      const void *s1;
  268.      const void *s2;
  269.      size_t len;
  270. {
  271.   op_t a0;
  272.   op_t b0;
  273.   long int srcp1 = (long int) s1;
  274.   long int srcp2 = (long int) s2;
  275.   op_t res;
  276.  
  277.   if (len >= OP_T_THRES)
  278.     {
  279.       /* There are at least some bytes to compare.  No need to test
  280.      for LEN == 0 in this alignment loop.  */
  281.       while (srcp2 % OPSIZ != 0)
  282.     {
  283.       a0 = ((byte *) srcp1)[0];
  284.       b0 = ((byte *) srcp2)[0];
  285.       srcp1 += 1;
  286.       srcp2 += 1;
  287.       res = a0 - b0;
  288.       if (res != 0)
  289.         return res;
  290.       len -= 1;
  291.     }
  292.  
  293.       /* SRCP2 is now aligned for memory operations on `op_t'.
  294.      SRCP1 alignment determines if we can do a simple,
  295.      aligned compare or need to shuffle bits.  */
  296.  
  297.       if (srcp1 % OPSIZ == 0)
  298.     res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
  299.       else
  300.     res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
  301.       if (res != 0)
  302.     return res;
  303.  
  304.       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
  305.       srcp1 += len & -OPSIZ;
  306.       srcp2 += len & -OPSIZ;
  307.       len %= OPSIZ;
  308.     }
  309.  
  310.   /* There are just a few bytes to compare.  Use byte memory operations.  */
  311.   while (len != 0)
  312.     {
  313.       a0 = ((byte *) srcp1)[0];
  314.       b0 = ((byte *) srcp2)[0];
  315.       srcp1 += 1;
  316.       srcp2 += 1;
  317.       res = a0 - b0;
  318.       if (res != 0)
  319.     return res;
  320.       len -= 1;
  321.     }
  322.  
  323.   return 0;
  324. }
  325.